/**
 * Binary Search 二分查找
 * https://leetcode-cn.com/problems/binary-search/
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let search = function (nums, target) {
  // 查找区间的左边界和右边界
  let l = 0
  let r = nums.length - 1
  let m
  while (l <= r) {
    // 这里为什么没有用 （l+r）/2，是避免数组超长时，l+r 会超过Integer的最大值
    // 这里Math.floor 或者 Math.round 或者Math.ceil都可，因为都会被遍历到
    m = Math.floor(l + (r - l) / 2)
    if (nums[m] === target) {
      return m
    } else if (target < nums[m]) {
      r = m - 1
    } else {
      l = m + 1
    }
  }
  return -1
}

let rslt = search([-1, 0, 3, 5, 9, 12], 12)

console.log(rslt)

//================v2要点总结===============
/**
 * 1. 二分查找的思想是，每次都取剩下的一半，来进行查找，每次都要进行分割处理的
 * 2. 明天重新实现一次
 */
